package leetcode.problems;

import java.util.HashSet;
import java.util.LinkedList;

/**
 * _0403 Merge Two Sorted Lists
 * 合并两个有序列表
 * Created by gmwang on 2018/3/23
 */
public class _0403MergeTwoSortedLists {
    /** 未使用
     * Mergewo sorted linked lists and return it as a new list.
     * The new list should be made by splicing together the nodes of the first two lists.
     *
     * 合并两个已排序的链表并将其作为一个新列表返回。新列表应该通过拼接前两个列表的节点来完成。
     *
     * Example:
     Input: 1->2->4, 1->3->4
     Output: 1->1->2->3->4->4
     */
    /**
     * 思路：
     * 1.   循环遍历两个listnode。获取的值放到集合中。
     * 2.   取出集合的值，构造listnode，每个值作为新建的listnode的下个结点。
     *      每次listnode = listnode.next
     * @param
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode listNode,next = new ListNode(0);
        listNode = next;
        LinkedList<Integer> list = new LinkedList<>();
        while(l1 != null || l2 != null){
            list.add(l1.val);
            list.add(l2.val);
            l1 = l1.next;
            l2 = l2.next;
        }
        while(!list.isEmpty()){
            listNode.next = new ListNode(list.pop());
            listNode = listNode.next;
        }
        return next.next;
    }

    public static void main(String[] args) {
        //初始化第一个Listnode
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2 ;
        ListNode listNode4 = new ListNode(4);
        listNode2.next = listNode4;
        //初始化第二个Listnode
        ListNode listNode11 = new ListNode(1);
        ListNode listNode13 = new ListNode(3);
        listNode11.next = listNode13;
        ListNode listNode14 = new ListNode(4);
        listNode13.next = listNode14;
        ListNode listNode = mergeTwoLists(listNode1, listNode11);
        while(listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
        HashSet<Object> objects = new HashSet<>();
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
